7504. Три прямоугольника

 

На белом листе бумаги в клетку нарисовали три закрашенных прямоугольника так, что их стороны лежат на линиях сетки, а вершины имеют известные целые координаты. Найти общее количество закрашенных клеток.

 

Вход. В трех строках содержится по четыре целых числа – координаты двух противоположных вершин каждого прямоугольника. Все числа по модулю не превышают 100.

 

Выход. Выведите одно число – количество закрашенных клеток.

 

Пример входа

Пример выхода

2 2 5 6

3 3 7 1

6 4 4 7

22

 

 

РЕШЕНИЕ

двумерный массив

 

Анализ алгоритма

Координаты вершин прямоугольников по модулю не превышают 100. Следовательно они принимают значения от -100 до 100. Сделаем сдвиг координат на вектор (100, 100) так чтобы все значения стали неотрицательными (теперь они изменяются от 0 до 200).

Координаты вершин во входных данных находятся в узлах сетки. Пронумеруем клетки по вертикали и горизонтали, начиная с 0. Тогда прямоугольник в узлах сетки (a, b) – (c, d) будет соответствовать прямоугольнику (a, b) – (c – 1, d – 1) на клетках.

Например, прямоугольнику (2, 2) – (5, 6) в узлах сетки соответствует прямоугольник (2, 2) – (4, 5) на клетках.

Объявим двумерный массив m[201][201]. Установим элемент m[i][j] = 1, если один из входных прямоугольников покрывает клетку (i, j). После обработки всех трех прямоугольников подсчитаем количество покрытых клеток.

 

Реализация алгоритма

Объявляем рабочий массив.

 

#define MAX 210

int m[MAX][MAX];

 

Функция swap меняем местами числа a и b.

 

void swap(int& a, int& b)

{

  int temp = a; a = b; b = temp;

}

 

Основная часть программы. Обнуляем массив m.

 

memset(m, 0, sizeof(m));

 

Последовательно обрабатываем три прямоугольника.

 

for (i = 0; i < 3; i++)

{

 

Читаем координаты очередного прямоугольника (a, b) – (c, d).

 

  scanf("%d %d %d %d", &a, &b, &c, &d);

 

Поменяем местами координаты так, чтобы (a, b) стал левым нижним углом, а (c, d) правым верхним. После этого будем иметь a < c и b < d.

 

  if (a > c) swap(a, c);

  if (b > d) swap(b, d);

 

Все клетки, которые покрываются прямоугольником (a, b) – (c – 1, d – 1), отмечаем в массиве m единицами. Координаты вершин сдвигаем на вектор (MAX / 2, MAX / 2), где MAX – размер массива (индексы массива не могут быть отрицательными).

 

  for (j = a; j < c; j++)

  for (k = b; k < d; k++)

    m[j + MAX / 2][k + MAX / 2] = 1;

}

 

В переменной res подсчитываем количество покрытых клеток.

 

res = 0;

for (i = 0; i < MAX; i++)

for (j = 0; j < MAX; j++)

  res += m[i][j];

 

Выводим ответ.

 

printf("%d\n",res);